/*
题目：最接近原点的K个数
给定一个数组 points ，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点，并且是一个整数 k ，返回离原点 (0,0) 最近的 k 个点。

这里，平面上两点之间的距离是 欧几里德距离（ √(x1 - x2)2 + (y1 - y2)2 ）。

你可以按 任何顺序 返回答案。除了点坐标的顺序之外，答案 确保 是 唯一 的。
https://leetcode.cn/problems/k-closest-points-to-origin
 */
class KClosest {
    public int[][] kClosest(int[][] points, int k) {
        //根据斜率构造大根堆
        PriorityQueue<int[]> heap = new PriorityQueue<>(new KComparator());

        for (int i = 0; i < k; i++) {
            int slope = Math.abs(points[i][0] * points[i][0] + points[i][1] * points[i][1]);
            int[] curArr = new int[] {points[i][0], points[i][1], slope}; //新建数组，包含x,y坐标和这个坐标的斜率

            heap.offer(curArr);
        }

        for (int i = k; i <points.length; i++) {
            int slope = Math.abs(points[i][0] * points[i][0] + points[i][1] * points[i][1]);
            int[] curArr = new int[] {points[i][0], points[i][1], slope}; //新建数组，包含x,y坐标和这个坐标的斜率

            if (heap.peek()[2] > curArr[2]) { //如果当前斜率小于堆顶斜率
                heap.poll();
                heap.offer(curArr);
            }
        }

        int size = heap.size();
        int[][] ret = new int[size][];
        for (int i = 0; i < size; i++) {
            int[] heapArr = heap.poll();
            ret[i] = new int[] {heapArr[0], heapArr[1]};
        }
        return ret;
    }
}

class KComparator implements Comparator<int[]> {
    @Override
    public int compare(int[] o1, int[] o2) {
        return o2[2] - o1[2];
    }
}
